package com.dycong.common.dataStructuresAndAlgorithms;

import java.util.*;

/**
 * Created by Duke on 2016/12/8.
 */
public class Ladder {

    public static void main(String[] args) {
        List<String> list = new LinkedList<>();
        list.add("zero");
        list.add("hero");
        list.add("here");
        list.add("hire");
        list.add("fire");
        list.add("five");
        Map<String, List<String>> map = new HashMap<>();
        map.put("zero", list);
        System.out.println(findChain(map, "zero", "five"));
    }


    public static List<String> findChain(Map<String, List<String>> adjacentWords, String first, String second) {
        Map<String, String> previousWord = new HashMap<>();
        LinkedList<String> q = new LinkedList<>();

        q.addFirst(first);
        while (!q.isEmpty()) {
            String current = q.removeFirst();
            List<String> adj = adjacentWords.get(current);
            if (adj != null) {
                ListIterator iterator = adj.listIterator();
                while (iterator.hasNext()){
                    if (iterator.next()==null){
                        String adjWord=iterator.next().toString();
                        previousWord.put(adjWord,iterator.next().toString());
                        iterator.previous();
                        q.addLast(adjWord);
                    }
                }
            }
        }

        previousWord.put(first, null);

        return getChainFromPreviousMap(previousWord, first, second);
    }

    public static List<String> getChainFromPreviousMap(Map<String, String> prev, String first, String second) {

        LinkedList<String> result = null;

        if (prev.get(second) != null) {
            result = new LinkedList<>();
            for (String str = second; str != null; str = prev.get(str))
                result.addFirst(str);
        }
        return result;

    }
}
